package leetcode.editor.cn;
//给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 
//
// 示例 1: 
//
// 输入: "abcabcbb"
//输出: 3 
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
// 
//
// 示例 2: 
//
// 输入: "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
// i
// 示例 3: 
//
// 输入: "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
// 
// Related Topics 哈希表 双指针 字符串 Sliding Window

import java.util.HashSet;
import java.util.Set;

/**
 * Java：无重复字符的最长子串
 *
 * @author：紫水木鱼
 * @createDate：2020-09-24 16:51:46
 */
class P3LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        Solution solution = new P3LongestSubstringWithoutRepeatingCharacters().new Solution();
        String str = "pwwkew";
        System.out.println(str + " 不含有重复字符的 最长子串 的长度是： " + solution.lengthOfLongestSubstring(str));
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int lengthOfLongestSubstring(String str) {
            int start = 0;//初始位置
            int end = 0; //结束位置
            int result = 0;//最终长度
            if (str == null || str == "") {
                return result;
            }
            //第一种方法,开始
//            int n = str.length();
//            int res = 0;
//            int end = 0, start = 0;
//            Set<Character> set = new HashSet<>();
//            while (start < n && end < n) {
//                if (set.contains(str.charAt(end))) {
//                    //start++,先用再加
//                    set.remove(str.charAt(start));
//                    start = start + 1;
//                } else {
//                    set.add(str.charAt(end));
//                    end = end + 1;
//                    res = Math.max(res, end - start);
//                }
//
//            }
//            第一种方法结束
//            第二种方法 开始

            // Map<String,Integer> map=new HashMap<>();//存放
            // //循环检索每一个字符，放入map中记录一下当前字符的位置，便于移动初始指针
            // for (int i = 0; i < str.length(); i++) {
            //     //获取当前字符串，
            //     String cur = String.valueOf(str.charAt(i));
            //     //判断map找那个是否含有该字符串，如果存在，则移动指针
            //     if (map.containsKey(cur)){
            //         //如果map中存放字符的位置小于当前指针位置，则不移动指针，反之亦然
            //         if (map.get(cur)>start){
            //             start=map.get(cur);
            //         }
            //     }
            //     //结束位置的指针 始终移动
            //     end=i+1;
            //     //取最大数
            //     result=Math.max(result,end-start);
            //     //将当前字符串的位置加1，便于下次重复的时候，初始指针的位置在初始指针的字符的下一个字符上
            //     map.put(String.valueOf(str.charAt(i)),end);
            // }
//            第二种方法结束
//            第三种方法开始

            // 如例题中“pwwkew”，刚进入这个队列满足条件的是“pw”，如果再进到下一步“w”,这时候的队列就变成了“pww”,
            // 显然已经不满足条件了。这时候就要移除队列左边的数，直到满足条件为止，“pww”=>“pw”=>“w”。
            // 继续之前再进入队列“wke”=>“wkew”=>"kew"。一直维持这样的队列，找出队列出现最长的长度。

            int length = str.length();
            Set<Character> set = new HashSet<>();
            while (start < length && end < length) {
                // try to extend the range [i, j]
                if (!set.contains(str.charAt(end))) {
                    set.add(str.charAt(end));
                    end++;
                    result = Math.max(result, end - start);
                } else {
                    set.remove(str.charAt(start));
                    start++;
                }
            }

//            第三种方法结束
            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}